package com.yulongtian.algorithms.binarysearch01;

/**
 * https://leetcode.cn/problems/peak-index-in-a-mountain-array/
 * 可
 *
 * @author yulongTian
 * @create 2023-02-01 9:47
 */
public class Test02 {
    public static void main(String[] args) {
//        int[] arr = {18, 29, 38, 59, 98, 100, 99, 98, 90};
        int[] arr = {0, 2, 1, 0};
//        int[] arr = {24, 69, 100, 99, 79, 78, 67, 36, 26, 19};
        System.out.println(peakIndexInMountainArray(arr));
    }

    //O(n)
    public static int peakIndexInMountainArray1(int[] arr) {
        int len = arr.length;
        int left = 0;
        int right = len - 1;

        while (left != right) {
            if (left + 1 < len - 1 && arr[left] < arr[left + 1]) {
                left++;
            }
            if (right - 1 >= 0 && arr[right - 1] > arr[right]) {
                right--;
            }
        }
        return left;
    }

    //O(log n)
    public static int peakIndexInMountainArray(int[] arr) {
        //二分法,先选择左右两下标。
        int left = 0;
        int right = arr.length - 1;
        int mid = 0;
        while (left < right) {
            mid = left + (right - left) / 2;
            //左右都小于mid，说明mid是山峰。
            if (arr[mid - 1] < arr[mid] && arr[mid] > arr[mid + 1]) break;
            //右边比左边高，说明山峰在右侧
            if (arr[mid + 1] > arr[mid]) left = mid;
                //右边比左边低，山峰在左侧
            else if (arr[mid + 1] < arr[mid]) right = mid;
        }
        return mid;
    }

}
